import java.util.Arrays;

public class MyHeap {
    public int[] elem;
    public int usedSize;

    public MyHeap(){
        this.elem = new int[10];
    }

    public void initElem(int[] array){
        for (int i = 0; i < array.length; i++) {
            this.elem[i] = array[i];
            this.usedSize++;
        }
    }

    public void createHeap(int[] array){
        for (int parent = (this.usedSize-1-1); parent >= 0 ; parent--) {
            shifDown(parent,this.usedSize);
        }
    }

    // 向下调整算法
    private void shifDown(int parent, int usedSize) {
        int child = parent * 2 + 1;
        while (child + 1 < usedSize && child < usedSize) {
            child = this.elem[child] > this.elem[child+1] ? child : child + 1;
            if(this.elem[child] > this.elem[parent]){
                Swap(elem,child,parent);
                parent = child;
                child = parent * 2 + 1;
            }else {
                break;
            }
        }
    }

    private void Swap(int[] elem,int x,int y){
        int tmp = this.elem[x];
        this.elem[x] = this.elem[y];
        this.elem[y] = tmp;
    }

    public void push(int val){
        if(isFull()){
            this.elem = Arrays.copyOf(elem,2*elem.length);
        }
        elem[usedSize] = val;
        shifUp(usedSize);
        usedSize++;
    }

    // 向上调整算法
    private void shifUp(int child) {
        int parent = (child - 1) >> 1;
        while (parent >= 0){
            if(elem[child] < elem[parent]){
                Swap(elem,child,parent);
                child = parent;
                parent = (child - 1) >> 1;
            }else {
                break;
            }
        }
    }

    private boolean isFull() {
        return this.usedSize == this.elem.length;
    }

    public int poll(){
        int val = elem[0];
        Swap(elem,0,usedSize-1);
        usedSize--;
        shifDown(0,this.usedSize);
        return val;
    }

    public int peek(){
        return elem[0];
    }

    // TopK 问题
    public int topK(int[] array,int k){ // 找到第三个大的数据 ， 建小堆
        int i = 0;
        for (i = 0; i < k; i++) {
            push(array[i]);
        }
        while(i < array.length){
            if(array[i] > peek()){
                poll();
                push(array[i]);
                i++;
            }
            i++;
        }

        return peek();
    }

}
